package top;

import java.util.*;

/**
 *
 * 关键点在于怎样保证删除list元素后，map里的索引不失效呢？
 * 就是把要删除的元素与最后一个元素换一下，然后更新最后一个元素的map碎银，再删掉最后一个，其他所索引就不会失效
 *
 *  @author chenyw
 * @date 2022/7/22 12:55
 */
public class Top380RandomizedSet {
    Map<Integer, Integer> map;
    Random random;
    List<Integer> list;

    public Top380RandomizedSet() {
        map = new HashMap();
        list = new ArrayList<>();
        random = new Random();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        list.add(val);
        map.put(val, list.size() - 1);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        int idx = map.get(val);
        int last = list.get(list.size() - 1);
        list.set(idx, last);
        map.put(last, idx);
        list.remove(list.size() - 1);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
}
